package tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import datastructure.binarytree.TreeNode;

public class NonRecursiveTraverse {
    public static List<String> preOrder(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<String> serialized = new ArrayList<>();
        stack.add(root);
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node == null) {
                serialized.add(null);
                continue;
            }
            serialized.add(node.val + "");
            if (node.right != null) {
                stack.add(node.right);
            } else {
                stack.add(null);
            }
            if (node.left != null) {
                stack.add(node.left);
            } else {
                stack.add(null);
            }
        }
        return serialized;
    }
}
